package 左哥算法.compare.华中农业;

// package niuke.edu.huazhongkejidaxue;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class B {

    // dfn序 + 60个树状数组
    static class BIT {
        int n;
        int[] arr;
        public BIT(int n) {
            this.n = n;
            this.arr = new int[n + 1];
        }
        int query(int p) {
            int r = 0;
            while (p > 0) {
                r += arr[p];
                p -= p & -p;
            }
            return r;
        }
        void update(int p, int d) {
            while (p <= n) {
                arr[p] += d;
                p += p & -p;
            }
        }
    }

    static int gTimestamp = 0;

    static void dfn(int u, int fa, List<Integer> []g, int[] start, int[] end) {
        start[u] = ++gTimestamp;
        for (int v: g[u]) {
            if (v == fa) continue;
            dfn(v, u, g, start, end);
        }
        end[u] = gTimestamp;
    }

    public static List<Long> fun(int n,int q,Integer[] nodes,Integer[][] edges,Integer[][] ops) {
        List<Long> list=new ArrayList<>();
        int[] arr = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            arr[i] = nodes[i-1];
        }

        List<Integer>[]g = new List[n + 1];
        Arrays.setAll(g, x->new ArrayList<>());
        // 1-index
        for (int i = 0; i < n - 1; i++) {
            int u = edges[i][0], v =edges[i][1];
            g[u].add(v);
            g[v].add(u);
        }

        int[] start = new int[n + 1];
        int[] end = new int[n + 1];
        dfn(1, -1, g, start, end);

        BIT[] bits = new BIT[61];
        Arrays.setAll(bits, x -> new BIT(n));
        for (int i = 1; i <= n; i++) {
            int v = arr[i];
            bits[v].update(start[i], 1);
        }
        for (int i = 0; i < q; i++) {
            if (ops[i][0] == 1) {
                int x = ops[i][1], y = ops[i][2];
                bits[arr[x]].update(start[x], -1);
                arr[x] = y;
                bits[arr[x]].update(start[x], 1);
            } else {
                int x = ops[i][1];
                int l =ops[i][2], r =ops[i][3];

                long res = 0;
                for (int j = l; j <= r; j++) {
                    res += bits[j].query(end[x]) - bits[j].query(start[x] - 1);
                }
                list.add(res);
            }
        }
        return list;
    }
    public static void compare(Fun fun){
        int count=10000;
        Random r=new Random();
        while (count-- > 0) {
            int n=r.nextInt(100)+1;
            int q=r.nextInt(100)+1;
            Integer[] nodes=new Integer[n];
            Integer[][] edges=new Integer[n-1][];
            Integer[][] ops=new Integer[100][];
            for (int i = 0; i < nodes.length; i++) {
                nodes[i]=r.nextInt(100);
            }
            for (int i = 0; i < q; i++) {
                int op = r.nextInt(2) + 1;
                switch (op){
                    case 1:
                        ops[i]=new Integer[]{op,r.nextInt(),r.nextInt()};break;
                    case 2:
                        ops[i]=new Integer[]{op,r.nextInt(),r.nextInt(),r.nextInt()};break;
                }
            }
        }
    }
    public static interface Fun{
        List<Long> fun(int n,int q,Integer[] nodes,Integer[][] edges,Integer[][] ops);
    }
}
